package 子集;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author: AirMan
 * @date: 2025/4/15 11:40
 * @description: 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * 说明：解集不能包含重复的子集。
 * 示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]
 */
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // 子集问题，回溯法解决，结果集是树的所有节点（组合问题和切割问题是树的叶子节点）
        // 求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

        // 回溯的参数：int[] nums，startIndex
        // 回溯的返回值：void
        // 回溯的终止条件：startIndex >= nums.length (该终止条件被合并到for循环中了)
        // 单层回溯的逻辑：
        // 横向遍历 nums 数组，从 startIndex 遍历到 nums.length，决定了递归的的次数（分支的数量）
        // 纵向遍历，每次将 startIndex 修改为 i + 1 的位置，递归之前都需要将当前的 path 添加到 result 中，因为所有的树节点都是结果集的一部分
        backtracking(nums, 0);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public void backtracking(int[] nums, int startIndex) {
        // 将该树节点添加至结果集中
        result.add(new ArrayList<>(path)); // 刚开始的时候就会将空集加入到 result 中
        if (startIndex >= nums.length) { // 终止条件可以不加
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            // 选取当前节点
            path.add(nums[i]);
            // 递归搜索，startIndex 更新为 i + 1 ，开辟一个新的分支
            backtracking(nums, i + 1);
            // 回溯，撤回当前选取的点，通过for循环重新选择后续的节点
            path.remove(path.size() - 1);
        }
    }
}
